package common.tree;

import java.util.*;
import java.util.function.Predicate;
import java.util.stream.Collectors;

/**
 * @author ：Sei
 * @date ：Created in 2020/1/6 15:28
 * @description：抽象树
 * @modified By：
 * @version: $
 */
public abstract class AbstractTree<K, N extends ITreeNode<K, N>> implements ITree<K, N> {

    Map<K, List<N>> mapByNodes(List<N> nodeList){
        return nodeList.stream().collect(Collectors.groupingBy(
                N::getParentKey
        ));
    }

    Map<K, N> mapByNodesSelf(List<N> nodeList){
        return nodeList.stream().collect(Collectors.toMap(
                N::getKey, n->n,
                (n1, n2)->n2, HashMap::new
        ));
    }

    protected List<N> bfs(N root, Predicate<N> searcher){
        Queue<N> queue = new LinkedList<>();
        queue.add(root);
        List<N> res = new LinkedList<>();
        while(!queue.isEmpty()){
        N currentNode = queue.poll();
        assert currentNode != null;
        for(N node : currentNode.getChilden()){
            if(searcher.test(node)){
                res.add(node);
            }
                queue.add(node);
            }
        }
        return res;
    }

    protected List<N> dfs(N root, Predicate<N> searcher){
        Deque<N> stack = new LinkedList<>();
        stack.add(root);
        List<N> res = new LinkedList<>();
        while(!stack.isEmpty()){
            N currentNode = stack.pollLast();
            assert currentNode != null;
            for(N node : currentNode.getChilden()){
                if(searcher.test(node)){
                    res.add(node);
                }
                stack.add(node);
            }
        }
        return res;
    }




}
